package com.leetcode.search.backtracking;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/7/27 17:16
 */
public class CombinationSum_39 {

    private int[] candidates;
    private final List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0)
            return res;
        Arrays.sort(candidates);
        this.candidates = candidates;
        backtrack(new LinkedList<>(), target, 0);
        return res;
    }

    private void backtrack(LinkedList<Integer> track, int target, int start) {
        if (0 == target) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target)
                break;
            track.offer(candidates[i]);
            // 每次传入本位的值，这样可以重复利用，同时可以进行剪枝
            // 通过传递差值来实现
            backtrack(track, target - candidates[i], i);
            track.removeLast();
        }
    }

}
